package Algorithms;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/*
    算法导论 - 归并排序
 */
public class MergeSort {
    /**
     * 合并函数
     *
     * @param list 数组
     * @param p    左下标
     * @param q    中间下标
     * @param r    右下标
     */
    private void merge(List<Integer> list, int p, int q, int r) {
        //复制
        ArrayList<Integer> l1 = new ArrayList<>(q - p + 1);
        ArrayList<Integer> l2 = new ArrayList<>(r - q);
        for (int i = p; i <= q; ++i) {
            l1.add(list.get(i));
        }
        for (int i = q + 1; i <= r; ++i) {
            l2.add(list.get(i));
        }
        //合并
        for (int i = p, left = 0, right = 0; i <= r; ++i) {
            //两个子队列都没到头
            if (left < l1.size() && right < l2.size()) {
                if (l1.get(left) > l2.get(right)) {
                    list.set(i, l2.get(right++));
                } else {
                    list.set(i, l1.get(left++));
                }
            }
            //左队列到头
            else if (right < l2.size()) {
                list.set(i, l2.get(right++));
            }
            //右队列到头
            else {
                list.set(i, l1.get(left++));
            }
        }
    }

    /**
     * 归并排序
     *
     * @param list 数组
     * @param p    左下标
     * @param r    右下标
     */
    public void sort(List<Integer> list, int p, int r) {
        if (p < r) {
            int middle = (r + p) / 2;
            sort(list, p, middle);
            sort(list, middle + 1, r);
            merge(list, p, middle, r);
        }
    }

    @Test
    public void test() {
        List<Integer> list = Arrays.asList(4, 2, 6, 98, 2, 5, 76, 8, 54, 3, 2453465, 3, 0);
        sort(list, 0, list.size() - 1);
        System.out.println(list);
    }
}
